import random
import time

from sort.Sort import Sort


class ShellSort(Sort):
    def __init__(self):
        super().__init__()

    def sort(self, arr_list):
        length = len(arr_list)
        step = length // 2
        # 循环步距
        while step > 0:
            # 循环数据,内部使用插入排序
            for i in range(step, length):
                temp = arr_list[i]
                insertIndex = i
                # 这里insertIndex > 0 避免的了到数组第一个数据的时候再去判断师傅位移
                while insertIndex > 0 and arr_list[insertIndex - step] > temp:
                    arr_list[insertIndex] = arr_list[insertIndex - step]
                    insertIndex -= step
                arr_list[insertIndex] = temp

            step //= 2
        return arr_list


if __name__ == '__main__':
    # arr = [2, 5, 3, 7, 1, 4]
    arr = [random.randint(0, 80000) * i for i in range(0, 80000)]
    # print(arr)
    start_time = time.time()
    sort = ShellSort()
    sort.sort(arr)
    print()
    print("希尔排序80000数据共计使用{}秒".format(str(int(time.time() - start_time))))
